// Package tree /*
/*

方法1：递归
时间复杂度：O(n) 要对n个节点进行操作
空间复杂度：O(n) 空间复杂度取决于递归调用栈，每一层递归实际只在root.Left, root.Right = root.Right, root.Left
这一步需要使用辅助变量，如果是满二叉树，则递归深度为log2N，如果二叉树成链状，则递归深度为N，所以最后空间复杂度为O(n)

case1:

r:


方法2：迭代
时间复杂度：
空间复杂度：

case1:

r:

*/
package tree

/*InvertTree
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func InvertTree(root *TreeNode) *TreeNode {
	if root == nil {
		return nil
	}
	root.Left, root.Right = root.Right, root.Left
	InvertTree(root.Left)
	InvertTree(root.Right)
	return root
}
